#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 10
#define maxdui 100

int dui[maxdui];
int front=0,rear=0;
int visited[max];

void endui(int x)
{
	dui[rear]=x;
	rear++;
}
int dedui()
{
	return dui[front];
	front++;
}
int duikong()
{
	if(front==rear)
		return 1;
	else
		return 0;
}
typedef struct Anode
{
	int i;
	Anode * next;
	int weight;
}anode;
typedef struct Vnode
{
	char c;
	anode * first;
}vnode;
typedef struct LIN
{
	vnode list[max];
	int vn;
	int an;
}lin;
void cre_lin(lin * pg)
{
	int i,j,weight;
	char start,end;
	scanf("%d%d",&pg->vn ,&pg->an );
	for(i=0;i<pg->vn ;i++)
	{
		scanf(" %c %c %d",&start,&end,&weight);
		anode * pa=NULL;
		pa=new anode;
		int istart,iend;
		istart=start-'A';
		iend=end-'A';
		pa->i =iend;
		pa->weight =weight;
		pa->next =NULL;

		anode * q=NULL;
		q=pg->list [istart].first ;
		if(q){
			pg->list [istart].first =pa;
		}
		else{
			while(q->next !=NULL){
				q=q->next ;
			}
			q->next =pa;
		}
	}
}

void print_lin(lin g)
{
	int i;
	anode * p=NULL;
	for(i=0;i<g.vn ;i++){
		printf("%c->",g.list [i].c );
		p=g.list [i].first ;
		while(p){
			printf("%c ",g.list [p->i ].c );
			p=p->next ;
		}
		printf("\n");
	}
}

int geti(lin g,char c)
{
	int i;
	for(i=0;i<g.vn ;i++){
		if(g.list [i].c ==c)
			return i;
	}
	return -1;
}

void df(lin g,char start)
{
	int v;
	v=geti(g,start);
	if(v==-1){
		printf("wrong\n");
		return;
	}
	int w;
	anode * p=NULL;
	visited[v]=1;
	printf("%c",g.list [v].c );
	p=g.list [v].first ;
	while(p){
		w=p->i ;
		if(visited[w]==0)
			df(g,g.list [w].c );
		p=p->next ;
	}
}
void Df(lin g,char start)
{
	int i;
	for(i=0;i<g.vn ;i++){
		visited[i]=0;
	}
	df(g,start);
	printf("\n");
	for(i=0;i<g.vn ;i++){
		visited[i]=0;
	}
}

void bf(lin g,char start)
{
	int v;
	v=geti(g,start);
	if(v==-1){
		printf("wrong\n");
		return;
	}
	anode * p=NULL;
	visited[v]=1;
	printf("%c",g.list [v].c );
	endui(v);
	int w;
	while(duikong!=0){
		v=dedui();
		p=g.list [v].first ;
		while(p){
			w=p->i ;
			if(visited[w]==0){
				visited[w]=1;
				printf("%c ",g.list [w].c );
				endui(w);
			}
			p=p->next ;
		}
	}
	printf("\n");
	int i;
	for(i=0;i<g.vn ;i++){
		visited[i]=0;
	}
}

void biao_to_zhen(lin g)
{
	int zhen[max][max];
	int i,j;
	anode * p=NULL;
	for(i=0;i<g.vn ;i++){
		for(j=0;j<g.vn ;j++)
			zhen[i][j]=0;
	}
	for(i=0;i<g.vn ;i++){
		p=g.list [i].first ;
		while(p){
			j=p->i ;
			zhen[i][j]=p->weight ;
			p=p->next ;
		}
	}
	for(i=0;i<g.vn ;i++){
		for(j=0;j<g.vn ;j++)
			printf("%5d",zhen[i][j]);
		printf("\n");
	}
}